#include <vector>

using namespace std;

class Solution {
public:
    //剑指 Offer 10- II. 青蛙跳台阶问题
    int numWays(int n) {
        int a = 1;
        int b = 1;
        int c = 1;
        for (int i = 2; i<=n; ++i)
        {
            c = (a+b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }

    //剑指 Offer 63. 股票的最大利润
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0)
        {
            return 0;
        }

        int size = prices.size();
        //vector<int> dp(size+1);
        //dp[0] = 0;

        int cost = 0;
        int minprices = 1e9;

        for (int i = 1; i<=size; ++i)
        {
            cost = max(cost, prices[i-1]-minprices);
            minprices = min(minprices, prices[i-1]);
        }
        return cost;
    }
};